0172. 阶乘后的零【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计算因子 5 的个数

1. 📝 题目描述

• leetcode

给定一个整数 n，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

---

示例 1：

输入：n = 3
输出：0
解释：3! = 6，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120，有一个尾随 0

示例 3：

输入：n = 0
输出：0

---

提示：

• 0 <= n <= 10^4

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

2. 🎯 s.1 - 计算因子 5 的个数

c

int trailingZeroes(int n) {
    int count = 0;
    while (n >= 5) {
        n /= 5;
        count += n;
    }
    return count;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
  let count = 0
  while (n >= 5) {
    n = Math.floor(n / 5)
    count += n
  }
  return count
}

py

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n >= 5:
            n //= 5
            count += n
        return count

• 时间复杂度：$O({\log }_{5}n)$
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 尾随零由因子 $2\times 5$ 产生，而因子 2 的数量远多于 5，所以只需计算因子 5 的个数
• $\lfloor n/5\rfloor +\lfloor n/25\rfloor +\lfloor n/125\rfloor +\cdots$ 累加直到商为 0